package com.algorithm.sort;

import java.util.Arrays;

/**
 * 归并排序的核心思想在于:
 * 1.分治
 * 2.将两个有序数组进行合并的时间复杂度为O(n)
 * 最大的优势:可以进行外存排序.(内存不能一次将所有数据放入时,可以拆分为多个文件单独排序,然后再合并)
 */
public class MergeSort {
    public static void main(String[] args) {
        Integer[] arr = {5,2,9,1,74,3,24,51,3,10};
        Integer[] temp = new Integer[arr.length];
        mergeSort(arr,0,arr.length -1,temp);
        System.out.println(Arrays.toString(arr));
    }

    /**
     *  @param arr
     * @param start
     * @param end
     * @param temp
     */
    private static void mergeSort(Integer[] arr, int start, int end, Integer[] temp) {
       if (start >= end){
           return;
       }
       int mid = (end +start)/2;
       mergeSort(arr,start,mid, temp);
       mergeSort(arr,mid +1,end, temp);
       merge(arr,start,mid,end,temp);
    }

    private static void merge(Integer[] arr, int start, int mid, int end, Integer[] temp) {
        int i = start;
        int index = start;
        int j = mid +1;
        while (i <= mid && j<= end){
            if (arr[i] <= arr[j]){
                temp[index++] = arr[i];
                i++;
            }else {
                temp[index++] = arr[j];
                j++;
            }
        }
        while (i<=mid){
            temp[index++] = arr[i++];
        }
        while (j<= end){
            temp[index++] = arr[j++];
        }
        for (int k = start; k <= end; k++) {
            arr[k] = temp[k];
        }
    }
    /**
     * 矛盾论.世界是辩证统一的,事情既具有矛盾性,又具有统一性.当我们想要去除其中一面只保留另外一面时,必然会遭受
     *
     *
     *
     *
     *
     */
}

